# 使用numpy模块生成随机数
import numpy as np
import time

def calcTime(func):
    '''
    函数修饰器, 用来计算算法的执行时间
    最终返回一个 list [temp, time_sum]
                    temp : 所有递增子列的列表
                    time_sum : 算法执行时间(单位ms)
    '''
    def warpper(nums):
        time_start = time.perf_counter()
        temp = func(nums)
        time_end = time.perf_counter()
        time_sum = time_end - time_start
        return [temp, time_sum *1000]
    return warpper

# 随机生成[1,10)的长度为n的分数数组nums  n>2
def nums(n):
    nums= np.random.randint(1, 10, size=n)
    return nums

#求解算法
@calcTime
def findSubsequences(nums):
    res = []
    path = []
    def backtrack(nums, startIndex):
        repeat = []                 # 这里使用数组来进行去重操作
        if len(path) >= 2:          # 子集问题上加上一个限制：至少有两个元素
            res.append(path[:])     # 切片复制 这里不要加return，取树上的节点
        for i in range(startIndex, len(nums)):
            if nums[i] in repeat:
                continue
            if len(path) >= 1:
                if nums[i] < path[-1]:
                    continue
            repeat.append(nums[i])  # 记录这个元素在本层用过了，本层后面不能再用了
            path.append(nums[i])
            backtrack(nums, i + 1)  # 递归
            path.pop()              # 回溯
    backtrack(nums, 0)
    return res

#测试
if __name__ == '__main__':
    num=nums(4)
    print(num)
    print(findSubsequences(num))

"""
测试结果：
        [2 8 3 5]
        [[[2, 8], [2, 3], [2, 3, 5], [2, 5], [3, 5]], 0.022199999999999998]
"""